﻿#define _CRT_SECURE_NO_WARNINGS 1


//518. 零钱兑换 II
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();

        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1])
                    dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
};

//优化
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();

        vector<int> dp(amount + 1);
        dp[0] = 1;

        for (int i = 1; i <= n; i++)
        {
            for (int j = coins[i - 1]; j <= amount; j++)
            {
                dp[j] += dp[j - coins[i - 1]];
            }
        }
        return dp[amount];
    }
};



//力扣::279. 完全平方数
class Solution {
public:
    int numSquares(int n) {
        int m = sqrt(n);

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][0] = 0;
        for (int j = 1; j <= n; j++)
            dp[0][j] = 0x3f3f3f3f;

        for (int i = 1; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= i * i)
                    dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        }

        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }

        return dp[m][n];
    }
};

//优化:
class Solution {
public:
    int numSquares(int n) {
        int m = sqrt(n);

        vector<int> dp(n + 1, 0x3f3f3f3f);
        dp[0] = 0;

        for (int i = 1; i <= m; i++)
        {
            for (int j = i * i; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
};


//力扣 474. 一和零
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));

        for (int i = 1; i <= len; i++)
        {
            //// 统计⼀下 0 1 的个数
            int a = 0;
            int b = 0;
            for (auto& x : strs[i - 1])
                if (x == '0') a++;
                else b++;
            for (int j = 0; j <= m; j++)
            {
                for (int k = 0; k <= n; k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= a && k >= b)
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
                }
            }
        }
        return dp[len][m][n];
    }
};

//优化
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i <= len; i++)
        {
            //// 统计⼀下 0 1 的个数
            int a = 0;
            int b = 0;
            for (auto& x : strs[i - 1])
                if (x == '0') a++;
                else b++;
            for (int j = m; j >= a; j--)
            {
                for (int k = n; k >= b; k--)
                {
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);
                }
            }
        }
        return dp[m][n];
    }
};


//力扣 879. 盈利计划
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int MOD = 1e9 + 7;
        int len = group.size();

        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));

        for (int j = 0; j <= n; j++)
            dp[0][j][0] = 1;

        for (int i = 1; i <= len; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                for (int k = 0; k <= minProfit; k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= group[i - 1])
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= MOD;
                }
            }
        }

        return dp[len][n][minProfit];
    }
};

//优化::
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int MOD = 1e9 + 7;
        int len = group.size();

        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));

        for (int j = 0; j <= n; j++)
            dp[j][0] = 1;

        for (int i = 1; i <= len; i++)
        {
            for (int j = n; j >= group[i - 1]; j--)
            {
                for (int k = minProfit; k >= 0; k--)
                {
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[j][k] %= MOD;
                }
            }
        }

        return dp[n][minProfit];
    }
};

//377. 组合总和 Ⅳ
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<double> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++)
        {
            for (auto x : nums)
            {
                if (i >= x)
                    dp[i] += dp[i - x];
            }
        }

        return dp[target];
    }
};


//96. 不同的二叉搜索树
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};